/// Source : https://leetcode.com/problems/minimize-malware-spread/description/
/// Author : liuyubobobo
/// Time   : 2018-10-13

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// DFS
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    int n;

public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {

        unordered_set<int> init_set;
        for(int e: initial)
            init_set.insert(e);

        n = graph.size();
        vector<bool> visited(n, false);

        int best = 0, res = -1;
        for(int v = 0; v < n; v ++)
            if(init_set.count(v)){
                int cnt = dfs(graph, v, visited);
                if(cnt > best){
                    best = cnt;
                    res = v;
                }
            }
        return res;
    }

private:
    int dfs(const vector<vector<int>>& g, int v, vector<bool>& visited){

        visited[v] = true;
        int res = 1;
        for(int next = 0; next < n; next ++)
            if(g[v][next] && !visited[next])
                res += dfs(g, next, visited);
        return res;
    }
};


int main() {

    return 0;
}